#include <iostream>
using namespace std;

struct VertexNode
{
    char vertex;       //数据域，顶点信息
    struct ArcNode *firstarc; //指针域，指向第一条弧
};
struct ArcNode
{
    int adjvex;       //数据域，邻接顶点下标
    struct ArcNode *nextarc; //指针域，指向下一个弧结点
};
const int MAXSIZE = 10;
template <class T>
class ALGraph
{
private:
    VertexNode adjlist[MAXSIZE];
    int vNum, arcNum; //顶点数目和弧的数目
    bool visited[MAXSIZE]={0};
public:
    ALGraph(ifstream &fin);
    ~ALGraph();
    void DFS(int v);
    void BFS(int v);
};
template <class T>
ALGraph<T>::ALGraph(ifstream &fin)
{
    fin >> vNum;
    fin >> arcNum;
    for (int k = 0; k < vNum; k++)
    {
        fin >> adjlist[k].vertex;
        adjlist[k].firstarc == NULL;
    }
    for (int k = 0; k < arcNum; k++)
    {
        int i, j;
        fin >> i >> j;
        ArcNode *s = new ArcNode;
        s->adjvex = j;
        s->nextarc = adjlist[i].firstarc;
        adjlist[i].firstarc = s;
    }
}
template <class T>
ALGraph<T>::~ALGraph()
{
    int i=0;
    while (i<vNum)
    {
        ArcNode *p=adjlist[i++].firstarc;
        while (p)
        {
            ArcNode *q=p->nextarc;
            delete p;
            p=q;
        }
    }
}
template <class T>
void ALGraph<T>::DFS(int v)
{
    cout<<adjlist[v].vertex;
    visited[v]=1;
    ArcNode *p=adjlist[v].firstarc;//p指向顶点v的第一条弧
    while (p)
    {
        int j=p->adjvex;
        if (visited[j]==0)
        {
            DFS(j);
        }
        p=p->nextarc;
    }
}
template <class T>
void ALGraph<T>::BFS(int v)
{
    int queue[MAXSIZE];
    int f=0,r=0;//生成空队列
    cout<<adjlist[v].vertex;
    visited[v]=1;
    queue[++r]=v;
    while (f!=r)
    {
        v=queue[++f];
        ArcNode *p=adjlist[v].firstarc;
        while (p)
        {
            int j=p->adjvex;
            if (visited[j]==0)
            {
                cout<<adjlist[j].vertex;
                visited[j]=1;
                queue[++r]=j;
            }
            p=p->nextarc;
        } 
    }
}